package com.zxyankh.leetcode.question.chinese;

import java.util.HashSet;
import java.util.Set;

/**
 * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 * <p>
 * 说明:
 * <p>
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * 给定数独序列只包含数字 1-9 和字符 '.' 。
 * 给定数独永远是 9x9 形式的。
 *
 * @author zxyAnkh
 */
public class No36 {
    public boolean isValidSudoku(char[][] board) {
        Set<Character> set = new HashSet<>(16);
        for (int i = 0; i < 9; i++) {
            if (!isValidSudoku(board, i, true, set) || !isValidSudoku(board, i, false, set)) {
                return false;
            }
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (!isValidSudoku(board, j, i, set) || !isValidSudoku(board, j, i, set)) {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean isValidSudoku(char[][] board, int row, boolean vertical, Set<Character> set) {
        if (vertical) {
            for (int i = 0; i < 9; i++) {
                if (board[row][i] == '.') {
                    continue;
                }
                if (set.contains(board[row][i])) {
                    set.clear();
                    return false;
                } else {
                    set.add(board[row][i]);
                }
            }
        } else {
            for (int i = 0; i < 9; i++) {
                if (board[i][row] == '.') {
                    continue;
                }
                if (set.contains(board[i][row])) {
                    set.clear();
                    return false;
                } else {
                    set.add(board[i][row]);
                }
            }
        }
        set.clear();
        return true;
    }

    private boolean isValidSudoku(char[][] board, int column, int row, Set<Character> set) {
        for (int i = row * 3; i < row * 3 + 3; i++) {
            for (int j = column * 3; j < column * 3 + 3; j++) {
                char c = board[i][j];
                if (c == '.') {
                    continue;
                }
                if (set.contains(c)) {
                    set.clear();
                    return false;
                } else {
                    set.add(c);
                }
            }
        }
        set.clear();
        return true;
    }
}
